package test230606;

import java.util.Arrays;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/6 0:22
 * 300. 最长递增子序列
 * https://leetcode.cn/problems/longest-increasing-subsequence/
 */
public class Solution01 {

    public int lengthOfLIS(int[] nums) {
        // 边界处理
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[] dp = new int[n];  // dp[i] 表示以 nums[i] 结尾的所有子序列的最大长度
        Arrays.fill(dp, 1);  // 每个位置自身可以成为子序列, 最小长度为 1
        // 动态规划过程
        int maxLen = 1;  // 存储最大长度
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j <= i - 1; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);  // 如果递增, 则新状态为 j 结尾的子序列的最大长度 + 1
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}
